package com.cet.algorithm.二叉树.路径总和;

import java.util.Stack;

/**
 * @program: algorithm
 * @description: 路径总和
 * @author: 陈恩涛
 * @create: 2022-07-25 10:58
 **/
public class LC112 {

    public static void main(String[] args) {

    }

    /**
     * 递归
     * @param root
     * @param targetsum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetsum) {

        if (root == null) {
            return false;
        }

        targetsum -= root.val;

        // 叶子结点
        if (root.left == null && root.right == null) {
            return targetsum == 0;
        }

        if (root.left != null) {
            boolean left = hasPathSum(root.left, targetsum);
            if (left) {
                // 已经找到
                return true;
            }
        }

        if (root.right != null) {
            boolean right = hasPathSum(root.right, targetsum);
            if (right) {
                // 已经找到
                return true;
            }
        }

        return false;
    }

    public boolean hasPathSum2(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        if (root.left == null && root.right == null) {
            return targetSum == root.val;
        }

        // 回溯
        return hasPathSum2(root.left, targetSum - root.val) || hasPathSum2(root.right, targetSum - root.val);
    }

    /**
     * 迭代法，先序遍历
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum3(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        final Stack<Object> stack = new Stack<>();
        stack.push(targetSum - root.val);
        stack.push(root);
        while (!stack.isEmpty()) {
            final TreeNode cur = (TreeNode) stack.pop();
            int tempSum = (int) stack.pop();
            if (cur.left == null && cur.right == null && tempSum == 0) {
                return true;
            }

            if (cur.right != null) {
                stack.push(tempSum - cur.right.val);
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(tempSum - cur.left.val);
                stack.push(cur.left);
            }
        }
        return false;
    }
}
